2021 百度之星初赛一

imily's notebook

2021-08-01

比赛

好诶又能水博客了！

拆点，转移关系写成矩阵，$k$ 好大 -> 快速幂，做完。

要按顺序拒绝操作

$f[i, x]$ 表示到 $i$ 操作，停在 $x$ 的最小拒绝数

执行交换 $x$、$y$ 的操作时，用彼此的 $f$ 更新一下。滚一维做完了。

赛时比较慌张，容易漏讨论怎么办呢？打表，对着表写

特判 $a = b$

$a \equiv b \pmod{c}$ -> $a - b \equiv 0 \pmod{c}$

枚举 $a - b$ 的因数即可。

我写的链表，每次假设询问的时候断掉再连上就可以了，轻松愉快

题解是说维护头俩 $0$ 的位置，填了其中一个就往后找到下一个 $0$，$O(n)$

模拟

以下是全场两位数 AC 嘚！一场初赛三道数数题、其中两道拉反，麻了（是这么用吧

枚举填非 $0$ 数字的位置：

$q(n) = \sum\limits_{k = 0}^n \binom{n}{k} \binom{2n - k}{n - k} 2^k c^k$

接下来都是化式子 + 多项式科技的事情了，我觉得我可以止于此步。~~才不会说是因为看不懂官解呢~~

考虑先将 $s$ 个儿子分配给 $m$ 个根 ($I$)，再把剩下的 $n - m$ 个点组合成 $s$ 棵有根树的方案 ($II$)

考虑 ($II$)，根据广义 cayley 定理（将 $n$ 个有标号节点形成 $k$ 棵有根树的方案数是 $kn^{n - k - 1}$）推得方案数

$= \binom{n - m}{s} s (n - m)^{n - m - s - 1} = \binom{n - m - 1}{s - 1} (n - m)^{n - m - s}$

再考虑 ($I$)，显然是 $s! [x^s] ( \sum\limits_{i = 0}^k \frac{x^i}{i!} )^m$

再往下是拉反和复合逆了，止步于此.jpeg